package org.usmile.algorithms.knapsack;

public class _Complete_Knapsack3 {
    public int solve(int[] weights, int[] values, int capacity) {
        int[][] dp = new int[weights.length][capacity + 1];
        for (int c = 0; c <= capacity; c++) {
            dp[0][c] = (c / weights[0]) * values[0];
        }

        for (int i = 1; i < weights.length; i++) {
            for (int c = 0; c <= capacity; c++) {
                int count = c / weights[i];
                for (int k = 0; k <= count; k++) {
                    dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - k * weights[i]] + k * values[i]);
                }
            }
        }

        return dp[weights.length - 1][capacity];
    }


    public static void main(String[] args) {
        _Complete_Knapsack3 k = new _Complete_Knapsack3();
        int[] w = {3, 4, 5, 2};
        int[] v = {15, 10, 12, 8};
        System.out.println(k.solve(w, v, 10));
    }
}
